// https://leetcode.cn/problems/odd-even-linked-list/
// Created by ade on 2022/10/28.
// 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 1,2,3,4,5,6,7
    // 1,2,3,4,5,6
    ListNode *oddEvenList(ListNode *head) {
        if (!head || !head->next) return head;
        ListNode *odd = head;
        ListNode *evenStart = head->next;
        ListNode *even = evenStart;
        while (1) {
            if (!odd->next) break;
            even = odd->next;
            if (!even->next) break;
            // 奇数相连
            odd->next = even->next;
            odd = even->next;
            // 偶数相连
            if (!odd->next) break;
            even->next = odd->next;
        }
        odd->next = evenStart;
        even->next = nullptr;
        return head;
    }

    ListNode *init() {
        ListNode *head = new ListNode(1);
        ListNode *index = head;
        for (int i = 2; i <= 6; i++) {
            ListNode *tmp = new ListNode(i);
            index->next = tmp;
            index = tmp;
        }
        return head;
    }

    void show(ListNode *head) {
        while (head) {
            cout << head->val << ",";
            head = head->next;
        }
        cout << endl;
    }
};

int main() {
    Solution so;
    ListNode *head = so.init();
    so.show(head);
    ListNode *sorted = so.oddEvenList(head);
    so.show(sorted);
    return 0;
}